1. Field of the Invention
The present disclosure relates generally to packet networks, and more particularly to the routing and switching of packets within such networks.
2. Description of Related Art
In a packet network, “nodes” or “routers” share network address information that allows each node or router to forward packets toward their respective destination networks. For networks defined using the Internet Protocol (“IP”), each node is provisioned with a network address that identifies the particular network the system is on, and with a system or host address that uniquely identifies the node. Destination endpoints are likewise identified by IP addresses. These IP addresses are shared among neighboring nodes to allow each router to build a “tree” with itself as the root node and next-hop paths from itself to every reachable network address. Internet Protocol network and host addresses are concatenated to form an IP address, with the network address forming the prefix of the IP address. Current implementations recognize a method of categorizing IP addresses known as Classless Inter-Domain Routing (CIDR), e.g., further described in Internet Engineering Task Force (IETF) Request for Comments (RFCs) 1518 and 1519, incorporated herein by reference. CIDR uses what is known as Variable-Length Subnet Masking (VLSM). VLSM allows the length of the network prefix in an IP address to have a variable length. A CIDR-compliant address is written as address/prefix bits, e.g., 192.168.0.0/16 specifies that the first 16 bits of 192.168.0.0 form a network address. When talking about prefix lengths in general, a network address is often shorthanded as “/x”, where “x” is the number of prefix bits. Thus a “/16 address” specifies that the first 16 bits of an IP address are significant.
CIDR allows multiple contiguous prefixes to be aggregated by a router. For instance, when a router R1 has route entries to networks 192.168.0.0/17 and 192.168.128.0/17, it may in some circumstances advertise a route to a network 192.168.0.0/16, which includes both subnetworks. This reduces the amount of routing information that must be sent to and tracked by router R1's neighbors, as the neighbors can replace two routes with one in their routing tables.
Routers use IP network addresses to forward routed traffic within a packet network “autonomous system” (AS) according to an interior routing (or gateway) protocol (an “IGP”). Generally, an AS comprises a set of routers that are commonly administered, communicate with each other using one or more common IGPs and routing metric sets, and communicate with routers outside of the AS using an inter-AS (or exterior) gateway protocol (“EGP”). Regardless of the internal AS architecture, the AS presents to the world outside the AS, through the EGP, a consistent picture of the destinations that are reachable through it. Some common routing protocols in use today include Open Shortest Path First (OSPF), Intermediate System to Intermediate System (IS-IS), and Border Gateway Protocol (BGP). OSPF is further described in Internet Engineering Task Force (IETF) Request for Comments (RFC) 2328, “OSPF Version 2,” by J. Moy, April 1998, and IETF RFC 2740, “OSPF for IPv6,” R. Coltun, December 1999, both of which are incorporated herein by reference. ISIS is further described in the International Organization for Standardization (ISO) document ISO 8473, “Intermediate System to Intermediate System Routing Information Exchange Protocol for Providing the Connectionless-mode Network Service,” ISO/IEC10589:2002, 2 nd Ed., which is incorporated herein by reference. BGP is further described in IETF RFC 4271, “A Border Gateway Protocol 4 (BGP-4),” by Y. Rekhter et al., January 2006, and is incorporated herein by reference.
OSPF and IS-IS are both IGPs and are examples of link-state protocols. A “link” can be considered to be an interface or port on a router (although some such protocols can be used to distribute other information). The state of that link contains a description of the interface and what routers/networks are reachable through that link. In OSPF, a link-state database contains the IP address of the interface/device, the subnet mask and other information describing the network, a list of routers connected to that network, a cost of sending packets across that interface, etc.
OSPF routers use link-state advertisements (LSAs) to share information from their link-state databases with neighboring routers in the same autonomous system. Whenever an interface is brought up or a change in outing information known to the router occurs, the router generates a LSA to inform its neighbors of the new or changed link-state information. When a neighbor router receives the LSA, it updates its own link-state database and then propagates the information in another LSA to its other neighbors. Thus the LSA is flooded to all routers, and all routers in the same area contain the same link-state database.
In order to place limits on the flooding of LSAs, OSPF allows routers in the same autonomous system to be grouped into areas. For instance, FIG. 1 depicts an autonomous system (AS) 100 divided into four areas AO, A1, A2, and A3. Every OSPF AS must have an area 0 or backbone area. Generally, all other areas connect to the backbone area, although provisions exist for transit areas.
Routers are classified according to their position in the AS. An internal router has all of its interfaces in the same area. In area A0, routers R1 and R2 are internal routers. Likewise, routers R8, R13 and R14, and RIO and RI 1, respectively are classified as internal routers in areas A1, A2, and A3. The internal routers maintain link-state databases containing all routing information distributed in their area, and all such link-state databases should be identical.
An area border router (ABR) has interfaces in multiple areas of the AS. R3 has two interfaces in area AO, and three interfaces in area A1, and is thus an ABR. Likewise R5 has two interfaces in area AO, and three interfaces in area A2, making it an ABR as well. Router R4 also has two interfaces in area AO, and three interfaces in area A3, classifying it as an ABR. Each ABR maintains a routing database for each area in which it maintains an interface. Each ABR also distributes some routing information between adjacent areas, including, where appropriate, summaries of routes.
An autonomous system boundary router (ASBR) has at least one interface in an area of the AS and at least one interface to another AS or running another routing protocol. The ASBR redistributes information received from the foreign network/protocol within OSPF. In FIG. 1, routers R6, R7, R9, and R12 are ASBRs. Router R6, for instance, communicates with a router R16 outside of the AS using eBGP (exterior BGP)
The Border Gateway Protocol (BGP) is currently the primary EGP used to route packets between the large numbers of ASes that, collectively, make up the “Internet.” BGP itself can function as either an interior gateway protocol or an exterior gateway protocol. When used as an EGP, BGP (“BGPe”) peers are located in different ASes. Each peer advertises to the other the networks/subnetworks that it can reach. BGP is a “path vector protocol”—BGP updates contain information detailing the AS-to-AS path that routing updates take to reach a router. From this path information, a BGP router can compare distance vectors for different possible routes to a destination and select a preferred route for each destination.
Each BGP speaker maintains a Routing Information Base (RIB) containing BGP update information. Within the RIB, unprocessed routing information received from the BGP speaker's peers is stored as “Adjacent-RIBs-In” information. As the BGP speaker processes the formation, it creates “Local-RIB” information, indicating the preferred routes that the BGP speaker has actually selected to use. From among these selected Local-RIB routes, the BGP speaker selects “Adjacent-RIBs-Out” information to be advertised to each specific peer. When two BGP speakers are first peered, each sends the other, through a set of updates, the entire appropriate contents of the Adjacent-RIBsOut database. Afterwards, incremental updates are used to inform the peer of new, changed, or withdrawn routes. Periodic KeepAlive messages exchanged by the peers insure each that the BGP connection is alive. Should the connection be closed for any reason by a BGP speaker, the speaker should send a Notification message, supplying a reason the connection is being closed, to the peer. When the BGP connection is closed, all routes that each peer has advertised to the other are removed from the RIB.
Although routing algorithms used by OSPF, IS-IS, and BGP provide one method to direct traffic across a packet network, other methods exist. For instance, protocols such as Multi-Protocol Label Switching (MPLS) allow packets to be routed across a packet network using small “labels” or “tags” inserted in the packets. Neighboring routers agree beforehand that packets transmitted from an upstream router to a downstream router with a given label will be forwarded along a unidirectional “label-switched path” (LSP). A LSP is essentially a tunnel set up between two “label edge routers” (LERs), one of which receives the packets and inserts the first label, and the other of which removes the last label and forwards the packet using other means (such as a traditional routing protocol). Other routers along the path are termed “label-switching routers” (LSRs), due to their function of switching incoming labels they recognize for outgoing labels that their downstream neighbor will recognize. Generally, the packets traversing a LSP belong to a common “Forwarding Equivalent Class” (FEC) that can be routed efficiently using the two LERs as points along the routing path.
FIG. 3 shows the same network diagram as FIG. 1, with three MPLS LSPs, MPLS1, MPLS2, and MPLS3 superimposed. Taking MPLS2 as exemplary, APR8 and R12 serve as label edge routers for the path. Routers R3, APR1, and R5 serve as label-switching routers for the path. Thus APR8 can send a packet to R12 by adding an MPLS label previously agreed upon by APR8 and R3, and forwarding the packet to R3. R3 recognizes the label as requiring that the packet be forwarded to APR1, with an MPLS label previously agreed upon by APR and R3. Two more similar hops deliver the packet to R12. R12 removes the MPLS label and forwards the traffic out an appropriate interface using, e.g., its stored routing information.
Interior and exterior gateway protocols, as well as label-switching protocols, ultimately direct packet flow through a router by installing routes in a Forwarding Information Base (FIB). FIBs are stored in some form of searchable memory that allows the router to quickly locate, for each received packet, an appropriate outgoing interface or interfaces, as well as packet-processing instructions.
As the used IP address space continues to grow, and also become more fragmented, each router in an AS is required to store an ever-increasing number of network routes in its FIB. Without some way to constrain the number of routes each router must know, the routers eventually reach a point where the physical memory available to store routes is exhausted.
A group of researchers associated with Cornell University has proposed a technique known as “Virtual Aggregation” that can be used to reduce FIB size for at least some routers in an AS. This technique is described in detail in “A White Paper on Reducing FIB Size through Virtual Aggregation,” P. Francis et al., June 2008, which is incorporated herein by reference. Virtual aggregation allows a subset of routers in an AS to serve as aggregation points (APs) for a given “virtual” network address prefix that is not physically aggregable because the real constituent prefixes underlying the given prefix do not all exit the AS and/or area at the same point. Routers in the same area as an AP receive the APs advertisements of a virtual network address prefix. When a receiving router knows no better route for a given packet than one belonging to the virtual network address prefix, it forwards the packet to the AP. The AP then uses a prearranged MPLS tunnel to forward the packet to the correct AS exit point.
FIGS. 2 and 3 present a virtual aggregation example. In FIG. 2, one router in each area assumes the role of an AP for a virtual prefix 10.130.1/24—these routers are labeled “APRx” and are depicted with a dashed “virtual route” to virtual prefix 10.130.1/24. Each router advertises the virtual route to other routers in its area. Each virtual router learns all actual routes underlying the virtual router, e.g., with an iBGP overlay scheme that allows some routers to learn a particular eBGP external route while others do not receive or ignore the external route. Thus in FIG. 2, APR8 learns that the network 10.130.1.64/26 is reachable through R7 and R16, the network 10.130.1/26 is reachable through R9 and R17, and the network 10.130.1.128/25 is reachable through R12 and R18. R3, R6, and R7 need not learn how to reach these subnetworks—traffic for all three is simply forwarded to APR8, which has advertised the larger virtual network 10.130.1/24.
APR8 maintains three MPLS LSPs corresponding to the three real subnetworks underlying the virtual address 10.130.1/24. As shown in FIG. 3, MPLS1 connects APR8 to R7, MPLS2 connects APR8 to R12, and MPLS3 connects APR8 to R9. Three FIB entries relate each real subnetwork to one of the three MPLS LSPs. When APR8 receives traffic having an address falling within the advertised virtual network, it matches the traffic with a FIB entry for the real subnetwork. The FIB entry instructs APR8 to MPLS-encapsulate a packet with an appropriate label and place it on the preconfigured LSP that connects the AP router to the appropriate AS edge router (for instance, MPLS2 to R12 for traffic addressed to network 10.130.1.128/25). The AS edge router deencapsulates the packet and forwards it out of the AS.
Routing using virtual aggregation is generally less efficient than direct routing, as the APR for a given virtual prefix will often not lie on a direct route to the egress point. This problem can be somewhat mitigated, while adding redundancy, by provisioning two APRs in an area to advertise and handle traffic for the same virtual aggregation. Additional routing efficiency can be obtained by identifying “popular prefixes,” e.g., those to which significant traffic is directed, and distributing direct IP routes for the popular prefixes to all routers in an area. For instance, if most of the traffic in the virtual prefix 10.130.1/24 was directed to the real prefix 10.130.1/26, all routers could be allowed to learn both the virtual prefix 10.130.1/24 and the real prefix 10.130.1/26. Direct routing would be used for the real prefix, and virtual routing for all other traffic within the virtual prefix.